mod wiggle_sort;
mod topological;

pub fn merge_sort(nums: &mut Vec<i32>) {
    let mut tmp_nums = vec![0; nums.len()];
    tmp_nums.copy_from_slice(nums);
    // sort tmp_nums data into nums
    top_down_split_merge(&mut tmp_nums, 0, nums.len(), nums);
}

// array A[] has the items to sort; array B[] is a work array
// end is exclusive
// sort data from B into A
fn top_down_split_merge(B: &mut Vec<i32>, start: usize, end: usize, A: &mut Vec<i32>) {
    if end - start <= 1 {
        return
    }
    let middle = (start + end) / 2;
    // sort half of data from A into B
    top_down_split_merge(A, start, middle, B);
    top_down_split_merge(A, middle, end, B);
    // merge data from B into A
    top_down_merge(B, start, middle, end, A);
}

// merge A data into B
fn top_down_merge(A: &mut Vec<i32>, start: usize, middle: usize, end: usize, B: &mut Vec<i32>) {
    let mut i = start;
    let mut j = middle;
    for k in start..end {
        if i < middle && (j >= end || A[i] <= A[j]) {
            B[k] = A[i];
            i += 1;
        } else {
            B[k] = A[j];
            j += 1;
        }
    }
    println!("merge {}-{}-{}", start, middle, end);
    for i in start..end {
        print!("{} ", B[i]);
    }
    println!();
}

#[test]
fn test_merge_sort() {
    let mut nums = vec![3, 4, 5, 1, 2];
    merge_sort(&mut nums);
    println!("{:?}", nums);
}

// 315
#[test]
fn test_count_of_smaller_numbers_after_self() {
    println!("{:?}", count_smaller(vec![5,2,6,1]))
}

// count-of-smaller-numbers-after-self
pub fn count_smaller(nums: Vec<i32>) -> Vec<i32> {
    // 记录数字原始的下标
    let mut indexed_val: Vec<(usize, i32)> = Vec::new();
    for (i, v) in nums.iter().enumerate() {
        indexed_val.push((i, *v));
    }
    // 映射原始下标的数字右侧比自己小的数
    let mut ans: Vec<i32> = vec![0; nums.len()];
    let mut tmp: Vec<(usize, i32)> = indexed_val.clone();

    merge_split_count(&mut indexed_val, 0, nums.len(), &mut tmp, &mut ans);
    return ans
}

// sort data from nums to tmp
fn merge_split_count(nums: &mut Vec<(usize, i32)>, begin: usize, end: usize, tmp: &mut Vec<(usize, i32)>, ans: &mut Vec<i32>) {
    if end - begin <= 1 {
        return;
    }
    let middle = (end + begin) / 2;
    merge_split_count(tmp, begin, middle, nums, ans);
    merge_split_count(tmp, middle, end, nums, ans);
    merge_sort_count(nums, begin, middle, end, tmp, ans);
}

// merge tmp[begin..middle] and tmp[middle..end] into nums
fn merge_sort_count(tmp: &mut Vec<(usize, i32)>, begin: usize, middle: usize, end: usize, nums: &mut Vec<(usize, i32)>, ans: &mut Vec<i32>) {
    let mut i = begin; // 左侧区间开始
    let mut j = middle;  // 右侧区间开始
    for k in begin..end {
        if i < middle && (j >= end || tmp[i].1 <= tmp[j].1) { // 注意 j >= end 和 tmp[i].1 <= tmp[j].1 不能写反了，不然tmp[j]可能越界
            // 当扫描到一个正序的数时，说明nums[begin..k]中已经放了 j - middle 个小于tmp[i].1的数
            ans[tmp[i].0] += (j - middle) as i32;
            nums[k] = tmp[i];
            i += 1;
        } else {
            nums[k] = tmp[j];
            j += 1;
        }
    }
}